class Solution:
    def maxProfit(self, prices) -> int:
        if len(prices) <= 1:
            return 0
        minPrices = min(prices[0], prices[1])
        dp = [0 for _ in range(len(prices))]
        dp[1] = max(dp[0], prices[1] - prices[0])
        for i in range(2, len(prices)):
            dp[i] = dp[i - 1]
            if prices[i] <= minPrices:
                minPrices = prices[i]
                continue
            for j in range(i):
                if prices[i] <= prices[j]:
                    continue
                if j == 0:
                    dp[i] = max(dp[i], prices[i] - prices[j])
                else:
                    dp[i] = max(dp[i], (prices[i] - prices[j]) + dp[j - 1])

        return dp[-1]


if __name__ == '__main__':
    so = Solution()
    t = [7,1,5,3,6,4]
    r = so.maxProfit(t)
    print(r)
